/*
 * @lc app=leetcode.cn id=1447 lang=typescript
 *
 * [1447] 最简分数
 */

// @lc code=start
function simplifiedFractions(n: number): string[] {
  // 获取最大公约数
  const gcd = (a: number, b: number): number => {
    return b === 0 ? a : gcd(b, a % b);
  };

  const ans = [];
  for (let i = 1; i <= n; i++) {
    for (let j = i + 1; j <= n; j++) {
      // 如果最大公约数为1，则说明最简分数
      if (gcd(i, j) !== 1) continue;
      ans.push(`${i}/${j}`);
    }
  }

  return ans;
}
// @lc code=end
